/*
给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。

输入：n = 2
输出：[0,1,1]
解释：
0 --> 0
1 --> 1
2 --> 10

输入：n = 5
输出：[0,1,1,2,1,2]
解释：
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

*/
#include<bits/stdc++.h>
using namespace std;
//自己的代码(不是用动态规划写的)
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int>ans;
        ans.push_back(0);
        if(n==0) return ans;
        ans.push_back(1);
        if(n==1) return ans;
        for(int i=2;i<=n;i++){
            int sum=0;
            int temp=i;
            do{
                if(temp%2==1) sum++;
                temp/=2;
            }while(temp);
            ans.push_back(sum);
        }
        return ans;
    }
};


/*
如果当前数字是偶数，则1的个数与当前数字 除以 2后数字的1的个数相同

即 dp[i] = dp[i >> 1]

如果当前数字是奇数，则1的个数是当前数字 除以 2后数字的1 的个数 + 1

即 dp[i] = dp[i >> 1] + 1

*/
class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1);
        for(int i = 0; i <= n; ++i) dp[i] = dp[i >> 1] + (i & 1);
        return dp;
    }
};
/*
&：将两个数都转换为二进制后，对每一位做判断，当连个书对应位均为1时，结果的对应位才为1，否则为0
    0  0 -->  0
    0  1 -->  0
    1  0 -->  0
    1  1 -->  1
*/

class Solution {
public:
    vector<int> countBits(int num) {
        // 预先开好空间
        vector<int> dp(num + 1);

        // 同样不需要从0开始，因为dp[0] = 0
        for(int i = 1; i <= num; i++){
            if(i % 2 == 0){ // 偶数
                dp[i] = dp[i / 2];
            }
            else{ // 奇数
                dp[i] = dp[(i - 1) / 2] + 1;
            }
        }
        
        // dp数组即为所求
        return dp;
    }
};

